/*!
 Temelia - Red-Black tree interface.

 Copyright (C) 2008, 2009 Ceata (http://ceata.org/proiecte/temelia).

 @author Dascalu Laurentiu

 This program is free software; you can redistribute it and
 modify it under the terms of the GNU General Public License
 as published by the Free Software Foundation; either version 3
 of the License, or (at your option) any later version.

 This program is distributed in the hope that it will be useful,
 but WITHOUT ANY WARRANTY; without even the implied warranty of
 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 GNU General Public License for more details.

 You should have received a copy of the GNU General Public License
 along with this program; if not, write to the Free Software
 Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301, USA.
 */

#ifndef RED_BLACK_TREE_H_
#define RED_BLACK_TREE_H_

#include "platform.h"
#include "binary_tree_common.h"

struct _red_black_tree_node_t;
typedef struct _red_black_tree_node_t *red_black_tree_node_t;

#ifndef BLACK
#define BLACK		0
#endif

#ifndef RED
#define RED			1
#endif

/*!
 * @see binary_tree_new
 */
DECLSPEC red_black_tree_t red_black_tree_new(void *key);

/*!
 * @see binary_tree_delete_node
 */
DECLSPEC void red_black_tree_delete_node(red_black_tree_t red_black);

/*!
 * @see binary_tree_delete
 */
DECLSPEC void red_black_tree_delete(red_black_tree_t red_black);

/*!
 * @see binary_tree_compare_trees
 */
DECLSPEC int red_black_tree_compare_trees(red_black_tree_t red_black1,
		red_black_tree_t red_black2, int compare(void *x, void *y,
				void *context), void *context);

/*!
 * @see binary_tree_is_empty
 */
DECLSPEC int red_black_tree_is_empty(red_black_tree_t red_black);

/*!
 * @see binary_tree_is_leaf
 */
DECLSPEC int red_black_tree_is_leaf(red_black_tree_t red_black);

/*!
 * @see binary_tree_get_size
 */
DECLSPEC int red_black_tree_get_size(red_black_tree_t red_black);

/*!
 * @see binary_tree_get_root
 */
DECLSPEC red_black_tree_t red_black_tree_get_root(red_black_tree_t red_black);

/*!
 * @see binary_tree_get_key
 */
DECLSPEC void *red_black_tree_get_key(red_black_tree_t red_black);

/*!
 * @brief Returns the color associated with this node.
 * Complexity O(1)
 *
 * @param Red-black tree
 */
DECLSPEC unsigned int red_black_tree_get_color(red_black_tree_t red_black);

/*!
 * @see binary_tree_get_parent
 */
DECLSPEC red_black_tree_t red_black_tree_get_parent(red_black_tree_t red_black);

/*!
 * @see binary_tree_get_left_child
 */
DECLSPEC red_black_tree_t red_black_tree_get_left_child(red_black_tree_t red_black);

/*!
 * @see binary_tree_get_right_child
 */
DECLSPEC red_black_tree_t red_black_tree_get_right_child(red_black_tree_t red_black);

/*!
 * @see binary_tree_get_height
 */
DECLSPEC int red_black_tree_get_height(red_black_tree_t red_black);

/*!
 * @see binary_tree_get_depth
 */
DECLSPEC int red_black_tree_get_depth(red_black_tree_t red_black);

/*!
 * @see binary_search_tree_search
 */
DECLSPEC red_black_tree_t red_black_tree_search(red_black_tree_t red_black, void *key,
		int compare(void *x, void *y, void *context), void *context);

/*!
 * @see binary_search_tree_insert
 */
DECLSPEC red_black_tree_t red_black_tree_insert(red_black_tree_t *red_black, void *key,
		int compare(void *x, void *y, void *context), void *context,
		int adjust_root);

/*!
 * @see binary_search_tree_remove
 */
DECLSPEC int red_black_tree_remove(red_black_tree_t *red_black_tree_, void *key,
		int compare(void *x, void *y, void *context), void *context,
		int adjust_root);

/*!
 * @see binary_search_tree_get_min
 */
DECLSPEC red_black_tree_t red_black_tree_get_min(red_black_tree_t red_black);

/*!
 * @see binary_search_tree_get_max
 */
DECLSPEC red_black_tree_t red_black_tree_get_max(red_black_tree_t red_black);

/*!
 * @see binary_tree_preorder
 */
DECLSPEC void red_black_tree_preorder(red_black_tree_t red_black, void key_handler(
		void *x, void *context), void *context);
/*!
 * @see binary_tree_inorder
 */
DECLSPEC void red_black_tree_inorder(red_black_tree_t red_black, void key_handler(
		void *x, void *context), void *context);

/*!
 * @see binary_tree_reverse_inorder
 */
DECLSPEC void red_black_tree_reverse_inorder(red_black_tree_t red_black,
		void key_handler(void *x, void *context), void *context);

/*!
 * @see binary_tree_postorder
 */
DECLSPEC void red_black_tree_postorder(red_black_tree_t red_black, void key_handler(
		void *x, void *context), void *context);

/*!
 * @see binary_tree_level_order
 */
DECLSPEC void red_black_tree_level_order(red_black_tree_t red_black, void key_handler(
		void *x, void *context), void *context);

/*!
 * @see binary_tree_show_indented
 */
DECLSPEC void red_black_tree_show_indented(red_black_tree_t red_black, void key_handler(
		void *x, int level, void *context), void *context);

#endif /* RED_BLACK_TREE_H_ */
